package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.common.printer.BinaryTreeInfo;
import com.tgy.common.printer.BinaryTrees;
import com.tgy.leetcode.TreeNode;

import java.util.Stack;

public class _09_调整搜索二叉树中两个错误节点 {

    private TreeNode preTreeNode;

    public TreeNode[] findErrorTreeNode(TreeNode root) {

        TreeNode[] errs = new TreeNode[2];
        find(root,errs);
        return errs;
    }


    private void find(TreeNode node, TreeNode[] errs) {

        if (node == null) {

            return;
        }

        find(node.left,errs);

        if (preTreeNode != null && preTreeNode.val > node.val ) {

            if (errs[0] == null) {

                errs[0] = preTreeNode;
            }

            errs[1] = node;
        }

        preTreeNode = node;
        find(node.right,errs);
    }

    public TreeNode[] findErrorParents(TreeNode root, TreeNode firstErrNode, TreeNode secondErrNode) {

        TreeNode[] parents = new TreeNode[2];

        if (root == null) {

            return parents;
        }

        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = root;
        while (true) {

            while (node != null) {

                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {

                break;
            }

            node = stack.pop();

            if (firstErrNode == node.left || firstErrNode == node.right) {

                parents[0] = node;
            }

            if (secondErrNode == node.left || secondErrNode == node.right) {

                parents[1] = node;
            }

            node = node.right;
        }

        return parents;
    }


    public TreeNode exchangeErrorNode(TreeNode root) {

        TreeNode newRoot = root;

        TreeNode[] errorTreeNodes = findErrorTreeNode(root);
        TreeNode[] errorParents = findErrorParents(root, errorTreeNodes[0], errorTreeNodes[1]);

        TreeNode firstErrorLeftNode = errorTreeNodes[0].left;
        TreeNode firstErrorRightNode = errorTreeNodes[0].right;

        TreeNode secondErrorLeftNode = errorTreeNodes[1].left;
        TreeNode secondErrorRightNode = errorTreeNodes[1].right;

        if (errorParents[0] != null && errorParents[1] != null) {

            if (errorParents[0] != errorTreeNodes[1] && errorParents[1] != errorTreeNodes[0]) {

                if (errorParents[0].left == errorTreeNodes[0]) {

                    errorParents[0].left = errorTreeNodes[1];
                }else {
                    errorParents[0].right = errorTreeNodes[1];
                }

                errorTreeNodes[1].left = firstErrorLeftNode;
                errorTreeNodes[1].right = firstErrorRightNode;

                if (errorParents[1].left == errorTreeNodes[1]) {

                    errorParents[1].left = errorTreeNodes[0];
                }else {
                    errorParents[1].right = errorTreeNodes[0];
                }

                errorTreeNodes[0].left = secondErrorLeftNode;
                errorTreeNodes[0].right = secondErrorRightNode;

            }else if (errorParents[0] == errorTreeNodes[1]){

                if (errorParents[1].left == errorTreeNodes[0]) {

                    errorParents[1].left = errorTreeNodes[0];
                }else {
                    errorParents[1].right = errorTreeNodes[0];
                }

                errorTreeNodes[0].left = errorTreeNodes[1];
                errorTreeNodes[0].right = secondErrorRightNode;

                errorTreeNodes[1].left = firstErrorLeftNode;
                errorTreeNodes[1].right = firstErrorRightNode;

            }else {


                if (errorParents[0].left == errorTreeNodes[0]) {

                    errorParents[0].left = errorTreeNodes[1];
                }else {
                    errorParents[0].right = errorTreeNodes[1];
                }

                errorTreeNodes[1].right = errorTreeNodes[0];
                errorTreeNodes[1].left = firstErrorLeftNode;

                errorTreeNodes[0].right = secondErrorRightNode;
                errorTreeNodes[0].left = secondErrorLeftNode;
            }

        }else if (errorParents[0] != null) {

            // errorParents[1] == null
            newRoot = errorTreeNodes[0];
            if (errorParents[0] == errorTreeNodes[1]) {

                errorTreeNodes[0].left = errorTreeNodes[1];
                errorTreeNodes[0].right = secondErrorRightNode;
            }else {

                if (errorParents[0].left == errorTreeNodes[0]) {

                    errorParents[0].left = errorTreeNodes[1];
                }else {
                    errorParents[0].right = errorTreeNodes[1];
                }

                errorTreeNodes[0].left = secondErrorLeftNode;
                errorTreeNodes[0].right = secondErrorRightNode;

            }

            errorTreeNodes[1].left = firstErrorLeftNode;
            errorTreeNodes[1].right = firstErrorRightNode;

        }else {

            // errorParents[1] == null
            newRoot = errorTreeNodes[1];

            if (errorParents[1] == errorTreeNodes[0]) {

                errorTreeNodes[1].right = errorTreeNodes[0];
                errorTreeNodes[1].left = firstErrorLeftNode;
            }else {

                if (errorParents[1].left == errorTreeNodes[0]) {

                    errorParents[1].left = errorTreeNodes[0];
                }else {
                    errorParents[1].right = errorTreeNodes[0];
                }

                errorTreeNodes[1].right = firstErrorRightNode;
                errorTreeNodes[1].left = firstErrorLeftNode;
            }


            errorTreeNodes[0].right = secondErrorRightNode;
            errorTreeNodes[0].left = secondErrorLeftNode;

        }

        return newRoot;
    }


    public static void main(String[] args) {

        /**
         *               6
         *             /   \
         *           1      10
         *          / \     / \
         *        0    8   3  12
         *
         *
         *        6.left = 1   1.left = 3.left 1.right = 3.right
         *
         *
         *               6
         *             /   \
         *           3      10
         *          / \     / \
         *        0    1   8  12
         *
         */
        TreeNode root = new TreeNode(0);

        root.left = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(3);

        root.right = new TreeNode(10);
        root.right.left = new TreeNode(8);
        root.right.right = new TreeNode(12);

        BinaryTrees.print(new BinaryTreeInfo() {
            @Override
            public Object root() {
                return root;
            }

            @Override
            public Object left(Object node) {
                return ((TreeNode)node).left;
            }

            @Override
            public Object right(Object node) {
                return ((TreeNode)node).right;
            }

            @Override
            public Object string(Object node) {
                return ((TreeNode)node).val;
            }
        });
        System.out.println();
//        System.exit(0);
        _09_调整搜索二叉树中两个错误节点 findErrorNode = new _09_调整搜索二叉树中两个错误节点();
        TreeNode newRoot = findErrorNode.exchangeErrorNode(root);
        BinaryTrees.print(new BinaryTreeInfo() {
            @Override
            public Object root() {
                return newRoot;
            }

            @Override
            public Object left(Object node) {
                return ((TreeNode)node).left;
            }

            @Override
            public Object right(Object node) {
                return ((TreeNode)node).right;
            }

            @Override
            public Object string(Object node) {
                return ((TreeNode)node).val;
            }
        });
    }

}
